package leetcode.weekly.week303;

import java.util.HashSet;
import java.util.Set;

//Solution4Test
public class Solution4 {

	public long countExcellentPairs(int[] nums, int k) {
		Set<Integer> set = new HashSet<>();
		for (int num : nums) {
			set.add(num);
		}
		int[] ns = new int[set.size()];
		int p = 0;
		for (int num : set) {
			ns[p++] = num;
		}
		int[] ones = new int[32];
		for (int i = 0; i < ns.length; i++) {
			int cnt = this.count(ns[i]);
			ones[cnt]++;
		}
		int[] sums = new int[32];
		sums[0] = ones[0];
		for (int i = 1; i < ones.length; i++) {
			sums[i] = sums[i - 1] + ones[i];
		}
		long ans = 0;
		for (int i = 0; i < ns.length; i++) {
			int cnt = this.count(ns[i]);
			int rest = k - cnt;
			if (rest < 1) {
				ans += sums[31];
			} else if (rest <=32) {
				int cnt1 = sums[31] - sums[rest - 1];
				ans += cnt1;
			}

		}
		return ans;
	}

	private int count(int num) {
		int ans = 0;
		while (num > 0) {
			if ((num & 1) == 1) {
				ans++;
			}
			num >>= 1;
		}
		return ans;
	}

	private int count(int num1, int num2) {
		int ans = 0;
		int p = 1;
		for (int i = 0; i < 31; i++) {
			int last1 = num1 & p;
			int last2 = num2 & p;
			if (last1 != 0 && last2 != 0) {
				ans += 2;
			} else if (last1 == 0 && last2 == 0) {
				ans += 0;
			} else {
				ans += 1;
			}
			p <<= 1;
		}
		return ans;
	}

}
